package alg;

import java.util.Arrays;

public class ALG07 {
   static class Solution {
        public int[] duplicateZeros(int[] arr) {
            int cur = 0,dest = -1;
            int n = arr.length;
            //先找到最后一个需要复写的数
            while(cur < n){
                if(arr[cur] == 0){
                    dest += 2;
                }else{
                    dest += 1;
                }
                if(dest >= n-1){
                    break;

                }

                cur++;
            }
            //处理一下边界条件
            if(dest == n){
                arr[n -1] = 0;
                cur--;
                dest -= 2;

            }
            //从前向后复写
            while(cur >= 0){
                if(arr[cur] != 0){
                    arr[dest--] = arr[cur--];
                }else{
                    arr[dest--] = 0;
                    arr[dest--] = 0;
                    cur--;
                }
            }
            return arr;
        }
    }

    public static void main(String[] args) {
        ALG07 alg07 = new ALG07();
        int[] arr = {1,0,2,3,0,4,5,0};
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.duplicateZeros(arr)));

    }
}
